#include<stdio.h>
#include<stdlib.h>
struct list
{
    int pre;
    int num;
    int next;
}chain[100001];
int main()
{
    int i, j = 0, head, n, tnode, tnum, tnext, end, first;
    scanf("%d%d", &head, &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d%d%d", &tnode, &tnum, &tnext);
        chain[tnode].num = tnum;
        chain[tnode].next = tnext;
        chain[tnext].pre = tnode;
        if (tnext == -1)
            end = tnode;
    }
    first = head;
    while (first != -1)
    {
        first = chain[first].next;
        j++;
    }
    n = j;
    while (n)
    {
        if (n == 1)
        {
            head = -1;
            printf("%05d %d %d\n", end, chain[end].num, head);
            break;
        }
        else
            printf("%05d %d %05d\n", end, chain[end].num, head);
        end = chain[end].pre;
        if (n == 2)
        {
            end = -1;
            printf("%05d %d %d\n", head, chain[head].num, end);
            break;
        }
        else
            printf("%05d %d %05d\n", head, chain[head].num, end);
        head = chain[head].next;
        n -= 2;
    }
    return 0;
}